The present invention relates generally to the field of compiler optimizations and more specifically to the enhancement of computer performance by decreasing the size of instruction code in frequently executed regions of code.
Buffers and caches are often used in computing systems to temporarily hold items that are frequently accessed or whose access time may otherwise inhibit performance. Since buffers and caches have limited size, techniques used to efficiently utilize their limited space strongly influence their performance. A cache is a small, fast memory close to a processor that contains information that has been recently accessed or is near information that has been recently accessed in the expectation that the accessed information and nearby information will be accessed in the near future. An instruction cache contains instructions, and a data cache contains data. If an item a processor needs is in a cache, the item can be accessed faster than if the item is in main memory or elsewhere, thus enhancing a processor's performance on a code. An efficiency of a cache depends on the nature of a code being executed and the number of items the cache contains.
Branch instructions in an instruction set architecture are usually of two varieties, a conditional branch and an unconditional branch. An unconditional branch causes a locus of control in a processor to jump from the execution of the unconditional branch to the instruction at the address of the target of the branch. An unconditional branch instruction is often termed a jump instruction. A conditional branch tests a condition in a processor that has been set during an execution of a preceding instruction to determine whether to “take the branch” and cause a locus of control to transfer to an instruction that does not immediately follow the branch, the “target”, or alternatively to “fall through the branch” and execute the instruction that immediately follows the conditional branch.
An instruction set architecture usually includes two types of conditional branch instructions, a “short-form” conditional branch that is a few bytes in length and has room for a few bits with which to encode a target's address, and is therefore limited to branch to a nearby target whose relative address can be encoded in the few bits, or a longer “long-form” conditional branch, with more bits available to encode a target's relative address, enabling a branch to an address of a target that is much farther away. A relative address is a quantity that is embedded in a conditional branch instruction that is added to the memory address of the conditional branch during the execution of a taken conditional branch to create an address of a target. A short-form conditional branch consumes less space in main memory and in an instruction cache (i-cache) enabling an i-cache of a given size to hold more instructions and therefore, be more efficient. Short-form conditional branches are used by a compiler when possible. If a target of a conditional branch is too distant from the conditional branch for a short-form conditional branch to be used, a long-form conditional branch is used.